package fun.coding.tree.bst;

import java.util.ArrayList;
import java.util.Queue;

import fun.coding.array.ArrayMain;

public class BinarySearchTreeMain {

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTreeImpl();
        
        BSTNode head = new BSTNode(10);
        bst.insert(head, 7);
        bst.insert(head, 6);
        bst.insert(head, 8);
        bst.insert(head, 12);
        bst.insert(head, 5);
        bst.insert(head, 11);
        bst.insert(head, 9);
        bst.insert(head, 4);
        
        System.out.println("in order traversal is ");
        bst.inOrderTraversal(head);

        System.out.println("pre order traversal is ");
        bst.preOrderTraversal(head);
        
        System.out.println("Trying to find 8, " + bst.find(head, 8));
        
        System.out.println("Trying to find 9," + bst.find(head, 9));
        
        System.out.println("find 3rd largest element ");
        bst.findKthLargestNode(head, 3);
        
        bst.printOutHuffmanCoding(head, 8);
        
        
        bst.levelOrderTraversal(head);
        System.out.println("level order using 2 queues");
        bst.levelOrderTraversalList(head);
        
        System.out.println();
        
        System.out.println("level order for certain level");
        bst.levelOrderPrintOneLevel(head, 2);
        
        
        //System.out.println("max height of the tree is " + bst.getTreeHeight(head));
        /*
        System.out.println("Flatten tree");
        bst.flatten(head);
        while(head != null) {
        	System.out.println(head.getValue());
        	head = head.getRight();
        }
        */
        /*
        System.out.println(bst.isBalanced(head));
        
        System.out.println(bst.isBST(head));
        
        System.out.println("building tree from pre and in order");
        int[] inOrder = {4, 10, 3, 1, 7, 11, 8, 2};
        int[] preOrder = {7, 10, 4, 3, 1, 2, 8, 11};
        
        BSTNode h = bst.buildBinaryTreeFromInOrderPreOrder(inOrder, preOrder, 0, 0, 8);
        bst.inOrderTraversal(h);
        
        System.out.println("total nodes in bst is " + bst.countBSTNode(head));
        System.out.println("total leaf nodes in bst is " + bst.countBSTLeaf(head));
        */
        ArrayList<Integer> res = bst.inOrderTraversalArray(head);
        ArrayMain.printArrayList(res);
        
        System.out.println(bst.maxPathSum(head));
    }
}
